// morris 实现 前序, 中序, 后序遍历二叉搜索树

import BST, { BstNode } from ".";
import { print, print2 } from "./test";

/**
 * 中序遍历
 * @param root
 */
export const inOrder = <T>(bst: BST<T>) => {
  // 获取根节点
  const root = bst.getRoot();

  // 树为空
  if (root === null) return;

  let p: BstNode<T> = root;

  /**
   * 获取前驱节点
   * @param p
   */
  const getAced = (n: BstNode<T>) => {
    if (n === null) return null;
    let left = n.left;

    // 右子节点存在并且右子节点不等于p
    while (left?.right != null && left?.right !== n) {
      left = left.right;
    }

    return left;
  };

  // 遍历
  while (p !== null) {
    if (p.left !== null) {
      // 左孩子不为空

      // 找到该节点的前驱节点
      const aced = getAced(p)!;

      // 不同的前驱节点做不同的处理
      if (aced.right === null) {
        aced.right = p;
        // 改变指向
        p = p.left;
      } else if (aced.right === p) {
        // 该前驱节点之前已经指向自己了, 说明当前自己是第二次遍历到

        // 访问该节点
        console.log(p.value);

        // 恢复原来的二叉树
        aced.right = null;

        // 重新将p 指向p.right;
        p = p.right!;
      }
    } else {
      // 左孩子为空

      // 访问该节点
      console.log(p.value);

      // 将p赋值为p.right
      p = p.right!;
    }
  }
};

/**
 * morris前序遍历
 * @param bst
 */
export const preOrder = <T>(bst: BST<T>) => {
  // 获取根节点
  const o = bst.getRoot();
  // 根节点为空
  if (o === null) return;

  // 拷贝一份新的二叉搜索树, 如果要求的是不影响原来的二叉树
  let root = bst.copy();

  // 拷贝一份
  let p = root;

  /**
   * 获取前驱节点
   * @param n
   */
  const getAced = (n: BstNode<T>) => {
    if (n === null) return;
    // 获取左子节点
    let left = n.left;

    while (left && left.right !== null) {
      left = left.right;
    }

    return left;
  };

  while (p !== null) {
    if (p.left !== null) {
      // 左子节点不为空
      console.log(p.value);
      // 找到前驱节点, 前驱节点的right指向p.right;
      const aced = getAced(p)!;

      // 前驱节点的right一定为空
      aced.right = p.right;

      // 重新指定p的指向
      p = p.left;
    } else {
      // 左子节点为空
      console.log(p.value);
      p = p.right!;
    }
  }
};

/**
 * 后序遍历
 * @param root
 */
export const postOrder = <T>(bst: BST<T>) => {
  // 获取根节点
  const root = bst.getRoot();

  // 树为空
  if (root === null) return;

  let p: BstNode<T> = root;

  /**
   * 对节点进行逆序
   * @param n
   */
  const reverseNode = (n: BstNode<T>) => {
    let pre: BstNode<T> | null = null,
      next: BstNode<T> | null = null;

    while (n !== null) {
      // n.right是下一个
      next = n.right!;

      // n.right赋值为之前的pre
      n.right = pre;

      // pre赋值为n
      pre = n;

      // n 赋值为next
      n = next;
    }

    // 返回pre
    return pre;
  };

  /**
   * 逆序打印节点n
   * @param n
   */
  const printNode = (n: BstNode<T>) => {
    // 对n进行逆序
    let n1 = reverseNode(n)!,
      n2 = n1;
    // 遍历
    while (n1 !== null) {
      console.log(n1.value);
      n1 = n1.right!;
    }

    // 重新调整过来
    reverseNode(n2);
  };
  /**
   * 获取前驱节点
   * @param p
   */
  const getAced = (n: BstNode<T>) => {
    if (n === null) return null;
    let left = n.left;

    // 右子节点存在并且右子节点不等于p
    while (left?.right != null && left?.right !== n) {
      left = left.right;
    }

    return left;
  };

  // 遍历
  while (p !== null) {
    if (p.left !== null) {
      // 左孩子不为空

      // 找到该节点的前驱节点
      const aced = getAced(p)!;

      // 不同的前驱节点做不同的处理
      if (aced.right === null) {
        aced.right = p;
        // 改变指向
        p = p.left;
      } else if (aced.right === p) {
        // 该前驱节点之前已经指向自己了, 说明当前自己是第二次遍历到

        // 恢复原来的二叉树
        aced.right = null;

        // 访问该节点
        // 逆序访问该节点的左子节点
        printNode(p.left);

        // 重新将p 指向p.right;
        p = p.right!;
      }
    } else {
      // 左孩子为空

      // 将p赋值为p.right
      p = p.right!;
    }
  }

  // p为空, 打印根节点
  printNode(root);
};

const bst = new BST();

bst.batchAdd([83, 89, 69, 86, 93, 28, 37]);

// bst.inOrder(undefined, (ele) => {
//     console.log(ele)
//     return false
// });

// // debugger
// print(bst)
// inorder(bst)
// print(bst)

// print(bst)
// preOrder(bst)
// print(bst)

print(bst);
postOrder(bst);
print(bst);
